package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description: 74. 搜索二维矩阵  {@literal https://leetcode-cn.com/problems/search-a-2d-matrix/}
 * @date: 2021/1/8 0008 15:09
 */
public class J0074_M_SearchMatrix {
    /*
    编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
    每行中的整数从左到右按升序排列。
    每行的第一个整数大于前一行的最后一个整数。

     */

    public static boolean searchMatrix(int[][] matrix, int target) {
            int row = matrix.length;
            if (row == 0) {
                return false;
            }
            int colLen = matrix[0].length;

            //先判断是不是左下角的数字
            int col = 0;
            while (col < colLen && row > 0) {
                int cur = matrix[row - 1][col];
                if (cur == target) {
                    return true;
                }
                //换到上一行
                if (cur > target) {
                    row--;
                } else {
                    //换到下一个数字
                    col++;
                }
            }
            return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,13,16,20},{23,30,34,60}};

        boolean b = searchMatrix(matrix, 13);
        System.out.println(b);

    }
}
